﻿//https://leetcode.cn/problems/remove-k-digits/?envType=problem-list-v2&envId=stack

class Solution {
public:
    string removeKdigits(string num, int k)
    {
        vector<char> v;
        for (auto& e : num)
        {
            //遍历到第i个位置，如果i-1位置的值大于i位置的，就删去i-1位置的值
            while (v.size() && v.back() > e && k)
            {
                v.pop_back();
                k -= 1;
            }
            v.push_back(e);
        }

        //如果走到了字符串的末尾，k还未减到0
        //说明整个数组现在是单调递增的，就要删去后面的k字符
        while (k--)
        {
            v.pop_back();
        }

        //提取元素组织返回结果
        string ret;
        int flag = 0; //判断前导零是否已经出现过
        for (int i = 0; i < v.size(); i++)
        {

            if (v[i] == '0' && flag == 0)
            {
                continue;
            }
            ret.push_back(v[i]);
            flag = 1;
        }

        return ret == "" ? "0" : ret;
    }
};